#include "FMath.h"

/**
 * 全排列
 */
std::vector<std::vector<int>> FMath::pFun(const std::vector<int>& a)
{
    std::vector<std::vector<int>> result;

    // 递归截至条件
    if(a.size() == 1)
    {
        result.push_back(std::vector<int>({a.front()}));
        return result;
    }

    // 一般情况
    for(int i=0; i<a.size(); ++i)
    {
        // 除去第一个元素之外的剩余元素进行全排列
        std::vector<int> b = a;
        std::vector<int>::iterator it = b.begin();
        b.erase(it + i);
        std::vector<std::vector<int>> ret = pFun(b);
        // 第一个元素+剩下的元素进行组装
        for(int j=0; j<ret.size(); ++j)
        {
            std::vector<int> one;
            one.push_back(a[i]);
            for(int k=0; k<ret[j].size(); ++k)
            {
                one.push_back(ret[j][k]);
            }
            result.push_back(one);
        }
    }
    return result;
}

/**
 * 组合
 */
std::vector<std::vector<int>> FMath::zFun(const std::vector<int>& a, int m)
{
    std::vector<std::vector<int>> result;

    // 递归截至条件
    if(m == 1)
    {
        for(int i=0; i<a.size(); ++i)
        {
            result.push_back(std::vector<int>({a[i]}));
        }
        return result;
    }

    // 一般情况
    for(int i=0; i<a.size(); ++i)
    {
        // 除去第一个元素之外的剩余元素进行选取(m-1)个
        std::vector<int> b = a;
        std::vector<int>::iterator it = b.begin();
        b.erase(it, it+i+1); // 尤其要注意这里，排列不讲究顺序，前面已经出现过的，后面就不要考虑了，12已经考虑过了，那么21就不用考虑了
        std::vector<std::vector<int>> ret = zFun(b, m-1);
        // 第一个元素+剩下的元素进行组装
        for(int j=0; j<ret.size(); ++j)
        {
            std::vector<int> one;
            one.push_back(a[i]);
            for(int k=0; k<ret[j].size(); ++k)
            {
                one.push_back(ret[j][k]);
            }
            result.push_back(one);
        }
    }
    return result;
}

/**
 * 排列：先组合，再分别全排列
 */
std::vector<std::vector<int>>  FMath::pzFun(const std::vector<int>& a, int m)
{
    std::vector<std::vector<int>> result;
    std::vector<std::vector<int>> z_result = zFun(a, m);
    for(int i=0; i<z_result.size(); ++i)
    {
        std::vector<std::vector<int>> ret = pFun(z_result[i]);
        for(int j=0; j<ret.size(); ++j)
        {
            result.push_back(ret[j]);
        }
    }
    return result;
}


/* Example 
int main()
{
    std::vector<int> arr = {1,2,3,4};
    // std::vector<std::vector<int>> ret = pFun(arr);
    std::vector<std::vector<int>> ret = zFun(arr, 2);
    //std::vector<std::vector<int>> ret = pzFun(arr, 2);
    for(std::vector<int>& v : ret)
    {
        for(int ele : v)
        {
            std::cout << ele << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}
*/
